/* 图的邻接表存储 */

int MaxSize = 100;  // 最大顶点数量

// 边表节点
struct EdgeNode
{
    int adjvertex;   //邻接点域
    EdgeNode *next;
};

// 顶点表节点
template <typename DataType>
struct VertexNode
{
    DataType vertex;
    EdgeNode *firstEdge;
};

// 邻接表
template <typename DataType>
class ALGraph
{
public:
public:
    ALGraph(DataType a[], int n, int e); // 构造函数
    ~ALGraph();  // 析构函数
    void DETraverse(int v);     // 深度优先遍历
    void BFTraverse(int v);     // 广度优先遍历
    void TopSort();             // 拓扑排序
private:
    VertexNode<DataType> adjlist[MaxSize];   // 存储顶点表的数组
    int vertexNum, edgeNum;     // 顶点数和边数
};


// 邻接表构造函数
template <typename DataType>
ALGraph<DataType>::ALGraph(DataType a[], int n, int e)
{
    int i,j,k;
    EdgeNode *s = nullptr;           // 声明边表节点
    vertexNum = n; edgeNum = n;
    // 初始化顶点表
    for (i = 0; i<vertexNum ; i++)
        adjlist[i].vertex = a[i]; 
        adjlist[i].firstEdge = nullptr;
    // 输入每一条边
    for(k = 0; k<edgeNum; k++)
    {
        std::cin >> i >> j;             // 输入边依附的两个顶点编号
        s = new EdgeNode;  s->adjvertex = j;   //生成边表节点s
        s->next = adjlist[i].firstEdge; // 将节点s插入表头
        adjlist[i].firstEdge = s;       // 更新第一条边
    }
}


// 邻接表析构函数
template <typename DataType>
ALGraph<DataType>::~ALGraph()
{
    EdgeNode *p  = nullptr , *q = nullptr;
    for(i = 0; i<vertexNum; i++)
    {
        p = q = adjlist[i].firstEdge;
        while (p != nullptr)
        {
            p = p->next;
            delete q;
            q = p;
        }
    }
}

// 深度优先遍历
template <typename DataType>
void ALGraph<DataType>::DETraverse(int v)
{
    int j;
    EdgeNode *p = nullptr;
    cout << adjlist[v].vertex; visited[v] = 1;
    p = adjlist[v].firstEdge;
    while(p != nullptr)
    {
        j = p->adjvertex;
        if(visited[j] == 0)
            DETraverse(j);
        p = p->next;
    }

}

// 广度优先遍历
template <typename DataType>
void ALGraph<DataType>::BFTraverse(int v)
{
    int w, j, Q[MaxSize];       // 采用顺序队列
    int front = -1, rear = -1;  // 初始化队列
    EdgeNode *p = nullptr;
    cout << adjlist[v].vertex; visited[v] = 1;  
    Q[++rear] = v;          // 被访问顶点入队
    while(front != rear)    // 当队列非空时
    {
        w = Q[++front];
        p = adjlist[w].firstEdge;       // 工作指针p指向顶点v的边表
        while(p != nullptr)
        {
            j = p->adjvertex;
            if(visited[j] == 0)
            {
                cout << adjlist(j).vertex;
                visited[j] = 1;
                Q[++rear] = j;
            }
            p = p->next;    
        }
    }
}


// 拓扑排序
template <typename DataType>
void ALGraph<DataType>::TopSort()
{
    int i,j,k,count = 0         // 累加器初始化
    int S[MaxSize] , top = -1;  // 采用顺序栈，初始化
    EdgeNode *p = nullptr;
    //
    for( i = 0; i<vertexNum; i++)
        if(adjlist[i].in == 0)
            S[++top] = i;       // 将入度为0的顶点压入栈
    while (top != -1)
    {
        j  = S[top--];  // 从栈中取出入度为0的顶点
        std::cout << adjlist[j].vertex;
        count++;
        p = adjlist[j].firstEdge;   // 工作指针p初始化
        // 不断扫描顶点表，找到顶点 j 的所有出边
        while (p != nullptr)
        {
            k  = p->adjvertex;
            adjlist[k].in--;
            if(adjlist[k].in == 0)
                S[++top] = k;       // 将入度为0的顶点压入栈
            p = p->next;            // 转去讨论下一个顶点
        }
    }
    // 迭代结束后，判断是否存在回路
    if(count << vertexNum)
        std::cout << "AOV中存在回路";
}